package com.itheima.leetcode;

import java.util.Arrays;

/**
 * <h1>买卖股票的最佳时机 IV</h1>
 * <h2>设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。</h2>
 * <h3>注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。</h3>
 */
public class SharesIVLeetcode188 {

    // 参考 122 题
    public static int maxProfit(int[] prices) {
        int i = 0;
        int j = 1;
        int sum = 0;
        while (prices.length > j) {
            if (0 < prices[j] - prices[i]) { // 有利润
                sum += prices[j] - prices[i];
            }
            i++;
            j++;
        }
        return sum;
    }

    static int maxProfit(int k, int[] prices) {
        /*
            第一次买，不依赖之前状态，以当日价格买入
            第一次卖，依赖于昨天第一次买 + 当日价格

            第二次买，依赖于昨天第一次卖 - 当日价格
            第二次卖，依赖于昨天第二次买 + 当日价格

            第三次买，依赖于昨天第二次卖 - 当日价格
            第三次卖，依赖于昨天第三次买 + 当日价格
            ...
         */
        if (prices.length / 2/* / 取地板 */ < k) {
            return maxProfit(prices);
        }
        int buy1 = Integer.MIN_VALUE;
        int sell1 = 0;
        int buy2 = Integer.MIN_VALUE;
        int sell2 = 0;
        int buy3 = Integer.MIN_VALUE;
        int sell3 = 0;

        int[] buy = new int[k];
        int[] sell = new int[k];
        Arrays.fill(buy, Integer.MIN_VALUE);

        for (int price : prices) {
            buy[0] = Math.max(buy[0], -price);
            sell[0] = Math.max(sell[0], buy[0] + price);

            for (int i = 1; i < k; i++) {
                buy[i] = Math.max(buy[i], sell[i - 1] - price);
                sell[i] = Math.max(sell[i], buy[i] + price);
            }
        }
        return sell[k - 1];
    }

    public static void main(String[] args) {
        System.out.println(maxProfit(2, new int[]{3, 2, 6, 5, 0, 3})); // 7
        System.out.println(maxProfit(2, new int[]{3, 3, 5, 0, 0, 3, 1, 4})); // 6
        System.out.println(maxProfit(4, new int[]{1, 2, 0, 1, 0, 3, 1, 4, 5})); // 9
    }
}
